14.6 並列コピー

並列コピーと並列マークの違い

同じオブジェクトが 2 回以上マークされてもたいていは無害

コピーは一度しか許されない

プロセッサ間での仕事の分割

レプリケーションGC［Blelloch and Cheng, 1999; Cheng and Blelloch, 2001; Cheng, 2001］を例に解説

概要

インクリメンタルコレクタや並行コレクタの一種

ミューテータが動いている間に生きているオブジェクトをコピーする

コレクションサイクル中にミューテータが書き換えた可能性のある、あらゆるフィールドの値を修正するような特別な仕組みを持っている

感想: 日本語壊れてる??

レプリケーションGCはどのようにコピー並列化を行うか

コピーを行うスレッドは、スレッド毎に仕事を積むスタックを持っている

負荷分散は、各スレッドが仕事を定期的にローカルなスタックと共有スタックの間で移動させることにより行う

単純な共有スタックでは、スタックにプッシュするスレッドとスタックからポップするスレッドの間で同期が必要になる

この同期はFetchAndAddなどのプリミティブな命令では不可能

しかし、プリミティブ命令しか使わなくても、複数のスレッドがスタックから要素をポップできるようにするか、あるいは、複数のスレッドがスタックに要素をプッシュできるようにするかのどちらかであれば実現できる

すべてのスレッドがスタックポインタを進めることしかしないか、すべてのスレッドがスタックポインタを戻すことしかしないから

pop (or push) はまとめて行える

いちいち同期をとるよりは効率的になるよね，というのが動機

code:copy_gc_using_stack_room.py

shared sharedStack # 仕事を積む共有スタック

sp ← 0 # ローカルのスタックポインタ

def worker_main():

while not terminated()

enterRoom() # ポップ部屋に入る

for i ← 1 to k

if isLocalStackEmpty()

acquireWork()

if isLocalStackEmpty()

break

performWork()

# 改善策を適用するとperformWork()がここに移る

# exitPopRoom()

# performWork()

# enterPushRoom()

transitionRooms() # pop room -> push room

generateWork()

if exitRoom() # プッシュ部屋から出る (この時点で local stack は empty)

terminate()

def acquireWork():

sharedPop() # 共有スタックから仕事を取ってくる

def performWork():

ref ← localPop()

scan(ref) # アルゴリズム 4-2 参照

def generateWork():

sharedPush() # 共有スタックを仕事に移す

def isLocalStackEmpty()

return sp = 0

def localPush(ref):

def localPop():

def sharedPop(): # 共有スタックから仕事を取ってくる

cursor ← FetchAndAdd(&sharedStack, sizeof(void*)) # 共有スタック上の仕事に「手を付ける」

if cursor ≧ stackLimit # 共有スタックが空

FetchAndAdd(&sharedStack, -sizeof(void*)) # スタックを戻す

else

def sharedPush(): # 仕事を共有スタックに移す

cursor ← FetchAndAdd(&sharedStack, -sp) - sp

for i ← 0 to sp - 1

sp ← 0

code:stack_room.py

# スレッドが取りうる状態は4つ

# - ポップ部屋の前で待っている

# - ポップ部屋の中

# - プッシュ部屋にいるが仕事をしてはいけない

# - ポップ部屋が空になるまで待ってる

# - プッシュ部屋でお仕事してる

shared gate ← OPEN

shared popClients # 現在ポップ部屋にいるクライアントの数

shared pushClients # 現在プッシュ部屋にいるクライアントの数

def enterRoom(): # enterRoomの呼び出しから戻った時点でポップ部屋に入る

while gate ≠ OPEN: # 最適化のためにしか機能してなさそう

# ポップ部屋の前で待っている状態

pass # 何もしない

FetchAndAdd(&popClients, 1) # ポップの開始を試みる

while gate ≠ OPEN:

FetchAndAdd(&popClients, -1) # 試みは失敗したので戻す

while gate ≠ OPEN:

# ポップ部屋の前で待っている状態

pass # 何もしない

FetchAndAdd(&popClients, 1) # 再度試みる

def transitionRooms(): # ポップ部屋からプッシュ部屋に移る

gate ← CLOSED

FetchAndAdd(&pushClients, 1)

FetchAndAdd(&popClients, -1)

while popClients > 0:

# プッシュ部屋にいるが仕事をしてはいけない

pass # 何もしない：ポップ中のクライアントがいなくなるまでプッシュを開始してはならない

def exitRoom(): # プッシュ部屋から出る

pushers ← FetchAndAdd(&pushClients, -1) - 1 # プッシュ停止

if pushers = 0: # 自分がプッシュ部屋に最後まで残っていた：終了判定をする

if isEmpty(sharedStack): # もう灰色のオブジェクトは残っていない

gate ← OPEN

return true

else:

gate ← OPEN

return false

else:

return false

コレクションのループの各イテレーションでは、スレッドはまず、ポップ部屋に入り、一定量の仕事をする

ポップ部屋では自身の走査するスロットをローカルスタックから取得するか、共有スタックから FetchAndAdd を使って取得する

新しく生成された仕事は自身のローカルスタックに追加する。

ポップ部屋から出て、他のすべてのスレッドがポップ部屋から出るのを待ってから、プッシュ部屋に入ろうとする

プッシュ部屋に最初に入ったスレッドは、gate を閉じて他のスレッドがポップ部屋に入るのを防ぐ。

プッシュ部屋に入ると、ローカルスタックの中身をすべて共有スタックに移す。

ここでも FetchAndAdd を使って共有スタック上の領域を予約する。

プッシュ部屋を最後に出るスレッドは gate を開く。

ナイーブな「部屋」の欠点とその改善

欠点

プッシュ部屋に入るのを待っているスレッドは、ポップ部屋に入っているすべてのスレッドが、担当オブジェクトを灰色にし終わるのを待たなければならない

オブジェクトを灰色にするのにかかる時間は、仕事を取得したり保存したりするのに比べると長い

プッシュフェーズに移行しようとしているプロセッサは、ポップフェーズにいるすべてのプロセッサが担当オブジェクトを灰色にし終わるのを待たなければならない

プロセッサ毎に担当オブジェクトを灰色にするのにかかる時間が大きく異なると、このような待ち時間の影響が大きくなる

改善策

プロセッサがポップ部屋を出てもプッシュ部屋に入らなくてもよいという抽象化も考えられる

オブジェクトを灰色にする作業は共有スタックとは関係ないので、部屋の外で行ってもよい

ポップ部屋が空になる可能性が増え、プッシュ部屋にスレッドが入れる可能性が増える

改善策の実装

transitionRoomsをexitPopRoomとenterPushRoomに分割して、その間でperformWorkする

プッシュ部屋用のゲートも必要になりそう

この改善策の欠点

終了判定が難しくなる

改善前は

プッシュ部屋から最後のスレッドが出る時には全スレッドのローカルスタックが空になっている

プッシュ部屋にスレッドがいる間はポップ部屋にスレッドが入ることはない

そのため、最後に部屋を出るスレッドが共有スタックも空かどうかを調べればよい

改善策を適用すると

コレクタスレッドは部屋の外で仕事をする可能性がある

プッシュ部屋から最後のスレッドが出る時に、あるスレッドTがポップ部屋から出て仕事をしており、プッシュ部屋にまだ入っていない、ということがあり得る

この抽象化では、いくつのスレッドが共有スタックからオブジェクトを持って行っているかを数えるグローバルなカウンタが必要になる

プッシュ部屋から最後に出るスレッドが、共有スタックが空かどうかに加えて、カウンタが 0 かどうかを調べる

オブジェクトの並列コピー

1 つのオブジェクトをコピーするスレッドが 1 つだけであることを保証するためには、スレッドがオブジェクトをコピーして、古いバージョンのヘッダに転送アドレスを書き込むという処理で競争をしなければならない

並列コピーの手法

レプリケーションGC (Blelloch and Cheng［1999])

スレッドがオブジェクトの転送ポインタのスロットに「ビジー」を示す値を書く競争をする。競争に勝ったスレッドはオブジェクトをコピーして、転送ポインタのスロットを複製のアドレスで上書きする

負けたスレッドは転送ポインタのスロットに有効なポインタが書き込まれるまでスピンして待たなければならない

GHCでの実験 (Marlow et al.［2008])

2つの手法を比較

競争した後にコピー

オブジェクトをコピーしようとするスレッドは、まずそのオブジェクトが転送されているかどうかを調べる。

ダミーglobalオブジェクトのアドレスとか?

CompareAndSwap が成功すると、オブジェクトをコピーし、to 空間の複製のアドレスを転送アドレスのスロットに書き込み、そのアドレスをリターンする。

CompareAndSwap で busy にするのに失敗すれば、そのスレッドは競争に勝ったスレッドがコピーし終わるまでスピンして待つ

コピーした後に競争

楽観的にオブジェクトをコピーしておき、その後で転送アドレスをCompareAndSwap で書き込む

CompareAndSwap に失敗すると、コピーを巻き戻さなければならない

比較結果

「コピーしたあとに競争」の方が若干良かった

「コピーしたあとに競争」のさらなる改善案

書き換え不可のオブジェクトについては、たまに二重にコピーされてしまうのを許す代わりに、書き込みに不可分操作を使わず、同期せずに書き込む方がよいのではないかと提案している

コレクタは世代別のコレクタであり、年長世代はマークコンパクト方式、年少世代はコピー方式で管理している

コピー方式の並列化

要求

コピー先の領域を割り当てる際の競合を最小限にする

生きているオブジェクトを一度だけしかコピーしてはならない

実装

コピー先の領域を割り当てる際の競合

年少世代での生存者空間へのコピーであっても、年長世代に昇格する場合であっても、スレッドローカルアロケーションバッファ（7.7 節参照）を用いることで最小化できる

スレッドローカルアロケーションバッファ

各スレッド固有のメモリ割付領域のこと

コピーは一度だけしか許されない

オブジェクトをコピーするときは、投機的にスレッドローカルアロケーションバッファに領域を割り付けて、それから CompareAndSwap を使って転送ポインタの書き込みを試みる。

CompareAndSwap が成功すれば、オブジェクトをコピーし、失敗すれば競争に勝ったスレッドが書き込んだ転送ポインタをリターンする

「コピーしたあとに競争」方式

NUMAにおけるメモリの局所性

(感想) ここで??

メモリ親和性ポリシー(memory affinity policy)

ファーストタッチ、ローカル

メモリを要求したスレッドが走っているプロセッサ(に近いメモリ)からメモリを割り付ける

ラウンドロビン

すべてのプロセッサから順にメモリを割り付ける

スレッドスケジューラ

プロセッサ親和性(processor affinity)を用いたスレッドスケジューラでは、スレッドを直前に実行したプロセッサにスケジュールしようとする。これによって局所性の性質はある程度保存される。

メモリマネージャ

ローカルのポリシーを使っても、NUMA を意識していないメモリマネージャはオブジェクトを適切に配置しないことがある

コピーGCでオブジェクトをコピーすることを考える

オブジェクトが割り付けられるメモリのaffinityがミューテータじゃなくてコレクタにひも付きがち

ローカルなポリシーでは、すべてのコピー先のオブジェクトはコレクタと同じプロセッサに割り付けられる

Ogasawara のメモリマネージャ

ヒープをいくつかのセグメントに区切る

各セグメントは複数ページ

それぞれのセグメントは単一のプロセッサにマップされる

ミューテータは、そのスレッドが走っているプロセッサのセグメントからメモリを確保する

コレクタスレッドは生きているオブジェクトを、常にそのオブジェクトにとって適切なプロセッサのセグメントに移動させる

コレクタは、それぞれのオブジェクトの最適なプロセッサを決定するために、支配スレッド（dominant-thread）情報も用いる

スタックの情報

ミューテータのスタックから直接参照されているオブジェクトの最適なプロセッサは、そのミューテータスレッドが走っているプロセッサである

ロックの情報

ロックの方式によっては、ロックしているスレッドの識別子をオブジェクトヘッダ中のワードに残す

ロックの実装をそういうふうに適切に変更・ラップする

直近(most recently)でオブジェクトをロックしたスレッドがわかる

同一スレッドは同一プロセッサにスケジュールされることが多いので適切なプロセッサもわかる

ポインタを手繰ることによる情報の伝搬

最適なプロセッサの情報を親オブジェクトから子オブジェクトに伝搬させる

https://gyazo.com/842cdce029db978c6b8947f8adef0f6e